package com.me.study.arithmeticAndDataStructure.sort;

import com.me.common.util.PrintUtil;

/**
 * 直接插入排序
 *
 * @author ME
 * @date 2019/2/22 15:00
 */
public class InsertSort {
    public static void directInsertSort(Integer[] array) {
        int tem = 0;
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            tem = array[i];

            // 从 arr[j] 开始依次（往前）和 arr[i] 比较，大的数放到 arr[j+1]，即：arr[j]大则后移，
            for (; j >= 0 && array[j] > tem; j--) {
                // 将大于array[i]的数整体后移一单位
                array[j + 1] = array[j];
            }
            // （经过循环之后 j-1）把 arr[i] 插入到空出来的位置上，即：arr[j] 没后移，放回原来的位置；arr[j] 后移了，则放到 arr[j] 上
            array[j + 1] = tem;
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] { 10, 5, 13, 7, 19 };
        System.out.println("原数组：");
        // Arrays.stream(array).forEach(System.out::println);
        PrintUtil.printArray(array);

        directInsertSort(array);

        System.out.println("排序后的数组：");
        PrintUtil.printArray(array);
    }

}
